package com.mxw.leetcode.A2nSum问题;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class A3nSum {

    /**
     * 如果假设输入一个数组 nums 和一个目标和 target，请你返回 nums 中能够凑出 target 的两个元素的值，
     * 比如输入 nums = [1,3,5,6], target = 9，那么算法返回两个元素 [3,6]。可以假设只有且仅有一对儿元素可以凑出 target。
     */
   static public List<List<Integer>> nSumTarget(int[] nums, int n, int start, int target) {

        int length = nums.length;
        List<List<Integer>> res = new ArrayList<>();

        // 至少是 2Sum，且数组大小不应该小于 n
        if (n < 2 || length < n) {
            return res;
        }

        // 2Sum 是 base case
        if (n == 2) {
            // 双指针那一套操作
            int left = start, right = length - 1;

            while (left < right) {

                int leftNum = nums[left], rightNum = nums[right];
                int sum=leftNum+rightNum;

                if (sum < target) {
                    while (left < right && nums[left] == leftNum) {
                        left++;
                    }
                } else if (sum > target) {
                    while (left < right && nums[right] == rightNum) {
                        right--;
                    }
                } else {
                    ArrayList<Integer> resTemp = new ArrayList<>();
                    resTemp.add(leftNum);
                    resTemp.add(rightNum);
                    res.add(resTemp);
                    while (left < right && nums[left] == leftNum) {
                        left++;
                    }
                    while (left < right && nums[right] == rightNum) {
                        right--;
                    }
                }
            }
        } else {
            // n > 2 时，递归计算 (n-1)Sum 的结果
            for (int i = start; i < length; i++) {
                List<List<Integer>> sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                for (List<Integer> arr : sub) {
                    // (n-1)Sum 加上 nums[i] 就是 nSum
                    arr.add(nums[i]);
                    res.add(arr);
                }
                while (i < length - 1 && nums[i] == nums[i + 1]) {
                    i++;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) throws Exception {
        int[] nums = {1, 3, 1, 2, 2, 3,6, -1, 5,-1};
        Arrays.sort(nums);
        List<List<Integer>> lists = nSumTarget(nums, 3, 0, 4);
        System.out.println(lists.toString());
    }
}
